#pragma once
#include "Allocator.h"
#include "Iterator.h"
#include "Trait.h"
#include "Algorithm.h"

namespace mini
{
	struct _List_node_base 
	{
		_List_node_base* pNext = nullptr;
		_List_node_base* pPrevious = nullptr;
	};

	template <typename T>
	struct _List_node : public _List_node_base 
	{
		T Data;
	};


	struct _List_iterator_base 
	{
		typedef size_t						size_type;
		typedef ptrdiff_t					difference_type;
		typedef bidirectionalIteratorTag	iterator_category;
		
		_List_node_base* mpBaseNode = nullptr;

		_List_iterator_base(_List_node_base* __x) : mpBaseNode(__x) {}
		_List_iterator_base() {}

		void increase() 
		{
			mpBaseNode = mpBaseNode->pNext;
		}
		void decrease() 
		{
			mpBaseNode = mpBaseNode->pPrevious;
		}

		bool operator==(const _List_iterator_base& __x) const 
		{
			return mpBaseNode == __x.mpBaseNode;
		}

		bool operator!=(const _List_iterator_base& __x) const 
		{
			return mpBaseNode != __x.mpBaseNode;
		}
	};


	template<class T, class _Ref, class _Ptr>
	struct _List_iterator : public _List_iterator_base 
	{
		typedef _List_iterator<T, T&, T*>             iterator;
		typedef _List_iterator<T, const T&, const T*> const_iterator;
		typedef _List_iterator<T, _Ref, _Ptr>         self;

		typedef T value_type;
		typedef _Ptr pointer;
		typedef _Ref reference;
		typedef _List_node<T> _Node;

		_List_iterator(_Node* __x) : _List_iterator_base(__x) {}
		_List_iterator() {}
		_List_iterator(const iterator& __x) : _List_iterator_base(__x.mpBaseNode) {}

		pointer operator->() const 
		{
			return &(operator*());
		}

		reference operator*() const 
		{
			return ((_Node*)mpBaseNode)->Data; 
		}

		self& operator++() 
		{
			this->increase();
			return *this;
		}
		self operator++(int)
		{
			self __tmp = *this;
			this->increase();
			return __tmp;
		}
		self& operator--() 
		{
			this->decrease();
			return *this;
		}
		self operator--(int) 
		{
			self __tmp = *this;
			this->decrease();
			return __tmp;
		}
	};

	template <typename T, typename Allocate>
	class TListBase
	{
	public:
		typedef Allocate allocatorType;
		allocatorType getAllocator() const
		{ 
			return allocatorType();
		}

		TListBase(const allocatorType&)
		{
			mpNode = _M_get_node();
			mpNode->pNext = mpNode;
			mpNode->pPrevious = mpNode;
		}
		~TListBase()
		{
			clear();
			_M_put_node(mpNode);
		}

		void clear()
		{
			_List_node<T>* __cur = (_List_node<T>*) mpNode->pNext;
			while (__cur != mpNode)
			{
				_List_node<T>* __tmp = __cur;
				__cur = (_List_node<T>*) __cur->pNext;
				_Destroy(&__tmp->Data);
				_M_put_node(__tmp);
			}
			mpNode->pNext = mpNode;
			mpNode->pPrevious = mpNode;
		}

	protected:
		typedef TAllocator<_List_node<T> > _Alloc_type;
		
		void _M_put_node(_List_node<T>* pNode)
		{
			_Alloc_type::deallocate(pNode, 1);
		}


		_List_node<T>* _M_get_node() 
		{
			return _Alloc_type::allocate(1);
		}


	public:
		_List_node<T>* mpNode;
	};

	template< typename T, typename Allocate = TAllocator<T> >
	class TList : protected TListBase<T, Allocate>
	{
	private:
		typedef TListBase<T, Allocate> _Base;
	protected:
		typedef void* voidPointer;
	public:
		typedef T value_type;
		typedef value_type* pointer;
		typedef const value_type* const_pointer;
		typedef value_type& reference;
		typedef const value_type& const_reference;
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;
		typedef _List_node<T> _Node;

		typedef typename _Base::_Alloc_type				allocatorType;
		typedef _List_iterator<T, T&, T*>				iterator;
		typedef _List_iterator<T, const T&, const T*>	const_iterator;
		
		/*
		typedef reverse_bidirectional_iterator<const_iterator, value_type, const_reference, difference_type>
			const_reverse_iterator;

		typedef reverse_bidirectional_iterator<iterator, value_type, reference, difference_type>
			reverse_iterator;
		*/

	public:
		TList( const Allocate& a = Allocate()): _Base( a ) {};
		~TList() 
		{
			clear();
		};
		allocatorType getAllocator() const
		{
			return _Base::getAllocator();
		}

		iterator insert(iterator __position, const T& __x) 
		{
			_Node* pTmp = createNode(__x);
			pTmp->pNext = __position.mpBaseNode;
			pTmp->pPrevious = __position.mpBaseNode->pPrevious;
			__position.mpBaseNode->pPrevious->pNext = pTmp;
			__position.mpBaseNode->pPrevious = pTmp;
			return pTmp;
		}
		void clear() 
		{
			_Base::clear(); 
		}
		iterator insert(iterator __position) 
		{
			return insert(__position, T());
		}

		iterator begin()
		{
			return (_Node*)(_Base::mpNode->pNext);
		}
		const_iterator begin() const
		{
			return (_Node*)(_Base::mpNode->pNext);
		}

		iterator end()
		{
			return _Base::mpNode;
		}
		const_iterator end() const
		{
			return _Base::mpNode;
		}
			
		iterator erase(iterator __position) 
		{
			_List_node_base* __next_node = __position.mpBaseNode->pNext;
			_List_node_base* __prev_node = __position.mpBaseNode->pPrevious;
			_Node* __n = (_Node*)__position.mpBaseNode;
			__prev_node->pNext = __next_node;
			__next_node->pPrevious = __prev_node;
			_Destroy(&__n->Data);
			_Base::_M_put_node(__n);
			return iterator((_Node*)__next_node);
		}

		iterator erase(iterator __first, iterator __last)
		{
			while (__first != __last)
			{
				erase(__first++);
			}
			return __last;
		}

		void push_front(T value)
		{
			insert(begin()); 
		}

		void push_back(const T& __x)
		{
			insert(end(), __x);
		}

		reference front() 
		{
			return *begin(); 
		}
		
		const_reference front() const
		{
			return *begin(); 
		}

		reference back() 
		{
			return *(--end()); 
		}
		
		const_reference back() const
		{
			return *(--end()); 
		}


		void push_back()
		{
			_Base::insert(end()); 
		}

		bool empty()
		{
			return _Base::mpNode->pNext == _Base::mpNode;
		}

		int size()
		{
			return command::distance(begin(), end() );
		}
		
		void resize(size_type __new_size, const T& __x)
		{
			iterator __i = begin();
			size_type __len = 0;
			//for (; __i != end() && __len < __new_size; ++__i, ++__len)
			//	;
			//if (__len == __new_size)
			//{
			//	erase(__i, end());
			//}
			//else                          // __i == end()
			//{
			//	insert(end(), __new_size - __len, __x);
			//}
		}
		
		void resize(size_type __new_size)
		{
			this->resize(__new_size, T()); 
		}

		
		void splice(iterator __position, TList& __x) 
		{
			if (!__x.empty())
			{
				this->transfer(__position, __x.begin(), __x.end());
			}
		}
		
		void splice(iterator __position, TList&, iterator __i) 
		{
			iterator __j = __i;
			++__j;
			if (__position == __i || __position == __j)
			{
				return;
			}
			this->transfer(__position, __i, __j);
		}

		void splice(iterator __position, TList&, iterator __first, iterator __last) 
		{
			if (__first != __last)
			{
				this->transfer(__position, __first, __last);
			}
		}


		void swap(TList<T, Allocate>& __x)
		{
			command::swap(_Base::mpNode, __x.mpNode);
		}
		
		void merge( TList<T, Allocate>& __x )
		{

		}
		void sort()
		{
			// Do nothing if the list has length 0 or 1.
			if (_Base::mpNode->pNext != _Base::mpNode &&
				_Base::mpNode->pNext->pNext != _Base::mpNode)
			{
				TList<T, Allocate> __carry;
				TList<T, Allocate> __counter[64];
				int __fill = 0;
				while (!empty()) 
				{
					__carry.splice(__carry.begin(), *this, begin());
					int __i = 0;
					while (__i < __fill && !__counter[__i].empty()) 
					{
						__counter[__i].merge(__carry);
						__carry.swap(__counter[__i++]);
					}
					__carry.swap(__counter[__i]);
					if (__i == __fill)
					{
						++__fill;
					}
				}

				for (int __i = 1; __i < __fill; ++__i)
				{
					__counter[__i].merge(__counter[__i - 1]);
				}
				swap(__counter[__fill - 1]);
			}
		}


	protected:
		void transfer(iterator __position, iterator __first, iterator __last)
		{
			if (__position != __last && __first != __last) 
			{
				// Remove [first, last) from its old position.
				__last.mpBaseNode->pPrevious->pNext = __position.mpBaseNode;
				__first.mpBaseNode->pPrevious->pNext = __last.mpBaseNode;
				__position.mpBaseNode->pPrevious->pNext = __first.mpBaseNode;

				// Splice [first, last) into its new position.
				_List_node_base* __tmp = __position.mpBaseNode->pPrevious;
				__position.mpBaseNode->pPrevious = __last.mpBaseNode->pPrevious;
				__last.mpBaseNode->pPrevious = __first.mpBaseNode->pPrevious;
				__first.mpBaseNode->pPrevious = __tmp;
			}

		}

		void _M_fill_assign(size_type __n, const T& __val)
		{
			iterator __i = begin();
			for (; __i != end() && __n > 0; ++__i, --__n)
			{
				*__i = __val;
			}

			if (__n > 0)
			{
				insert(end(), __n, __val);
			}
			else
			{
				erase(__i, end());
			}
		}

	private:
		_Node* createNode(const T& __x)
		{
			_Node* pNode = _Base::_M_get_node();

			_Construct(&pNode->Data, __x);

			return pNode;
		}

		_Node* createNode()
		{
			_Node* pNode = _Base::_M_get_node();
			_Construct(&pNode->Data);
			return pNode;
		}
	};

}
